// 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
// candidates 中的数字可以无限制重复被选取。

// 说明：
// 所有数字（包括 target）都是正整数。
// 解集不能包含重复的组合

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */

 // 暴露接口
function combinationSum(candidates: number[], target: number): number[][] {
    const res: number[][] = []; // 结果数组
    const path: number[] = []; // 当前路径数组
    let begin: number = 0; // 当前数组的最右索引，即搜索的起点
    combinationSum_DFS(candidates, target, res, path, begin);
    return res;
};
// 深度优先遍历回溯算法
function combinationSum_DFS(candidates: number[], target: number,
    res: number[][], path: number[], begin: number) {
    // 递归出口
    if (target <= 0) {
        // 如果目标值减为0
        if (target === 0) {
            res.push(Array.from(path)); // 推入浅拷贝
        }
        return;
    }
    for (let i = begin; i < candidates.length; i++) {
        path.push(candidates[i]);
        combinationSum_DFS(candidates, target - candidates[i], res, path, begin);
        begin++;
        // 回溯算法部分
        path.pop();
    }
}

// 这道题目其实也是一道值得多看的套路模板例题
// 基本的框架仍是限定于深度优先搜索结合回溯算法的大框架下
// 在深度优先遍历变化的过程中，遍历所有可能的列表并判断当前列表是否符合题目的要求
// 每搜索到一个数，我们就让target做对应的减法
// 我们以target作为递归考虑的终点，显然当target小于等于0，再往下搜下去就没有必要
// 我们做的部分就是判断当target = 0的时候将当前路径加入结果数组
// 展开分支的时候，由于题目中说每一个元素可以重复使用，我们考虑了所有的候选数，因此出现了重复的列表
// 可不可以在搜索的时候就去重呢？答案是可以的。
// 遇到这一类相同元素不计算顺序的问题，我们在搜索的时候就需要按某种顺序搜索。
// 具体的做法是：每一次搜索的时候设置下一轮搜索的起点begin，这是于循环起点中限定的
// 结果是从每一层的第 2 个结点开始，都不能再搜索产生同一层结点已经使用过的 candidate 里的元素
// 这里要注意的就是：
// 不讲究顺序（即 [2, 2, 3] 与 [2, 3, 2] 视为相同列表时），需要按照某种顺序搜索，此时使用 begin 变量
